/**
 *给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 *
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 *https://leetcode.cn/problems/remove-invalid-parentheses/description/
 */
class RemoveInvalidParentheses {

    public List<String> removeInvalidParentheses(String s) {
        List<String> ret = new ArrayList<>();
        Set<String> set = new HashSet<>();
        set.add(s);
        while(!set.isEmpty()) {
            for(String tmp : set) {
                if(isVail(tmp)) {
                    ret.add(tmp);
                }
            }
            if(ret.size()>0) {
                return ret;
            }
            Set<String> nextSet = new HashSet();
            for(String cur : set) {
                for(int i = 0;i<cur.length();i++) {
                    if(i>0 && cur.charAt(i)==cur.charAt(i-1)) {
                    continue;//如果相邻两个括号是一样的，那就只要删除一次就行了，比如：()),删除第二变成（），删除第3个也是()，所以没必要
                }
                if(cur.charAt(i)=='(' || cur.charAt(i) ==')') {
                    nextSet.add(cur.substring(0,i) + cur.substring(i+1));
                }
                }
            }
            set = nextSet;
        }
        return ret;
    }

    private boolean isVail(String s)
    {
        char[] ch = s.toCharArray();
        int count = 0;
        for(int i = 0;i<ch.length;i++) {
            if(ch[i] == '(') {
                count++;
            } else if(ch[i] ==')') {
                count--;
            }
            if(count < 0) {
                return false;
            }
        }
        return count==0;
    }
}